/*
 * com.future CO.,ltd.
 */

package com.future;

import java.util.Arrays;

/**
 * Description: 41. ȱʧ�ĵ�һ����������ˢ���14��
 * ����һ��δ������������� nums �������ҳ�����û�г��ֵ���С����������
 * <p>
 * ����ʵ��ʱ�临�Ӷ�Ϊ O(n) ����ֻʹ�ó����������ռ�Ľ��������
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺nums = [1,2,0]
 * �����3
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/first-missing-positive
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/5/2:18:28
 */
public class Solution_41 {

    public static void main(String[] args) {
        int[] arr = {7, 8, 9, 11, 12};
       /* arr = new int[]{3, 4, -1, 1};
        arr = new int[]{0};*/
        System.out.println(firstMissingPositive(arr));
    }

    /**
     * ˼·��
     * ά��һ����Ч�ڣ�0~R����Ч��������Ч����R+1~nums.length��
     * ���±�0~R��Ӧ��ֵ�ϸ�Ϊ1~R+1����ô�±�R+1��Ӧ��ֵ���Ǵ�
     * <p>
     * 1����ʼʱ�����������鶼����Ч�����ֱ��¼ָ����β�ڵ��L,R
     * 2��һ�α��������±�L��Ӧ��ֵ�������������
     * 2.1 num[L]==L+1,���±��0~n-1����Ӧ��ֵ�ֱ���1~n
     * 2.2 �������
     * �����nums���ֳ�(...L....R....nums.length)
     * a��ֵ������...L
     * b��ֵ��R...nums.length
     * c����L...R�����ظ�ֵ
     * 2.3 ��Ч���Ľ�����ֵ��L...R�����ڽ���
     *
     * @param nums
     * @return
     */
    public static int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        int L = 0;
        int R = nums.length;
        while (L != R) {
            System.out.println("L=" + L + ",R=" + R + "arr : " + Arrays.toString(nums));
            int val = nums[L];
            if (val == L + 1) {
                L++;
            } else if (val <= L || val > R || nums[val - 1] == val) {
                /**
                 * ���������
                 * 1��val<=L��L��߶��ϸ��1~L+1�ˣ��������һ��ֵ��1~L+1���䣬�Ǿ���Ҫ�����ҵ�-1
                 * eg: {1,2,2,4,9}
                 * ��L=2,R=5�ǣ���Ϊnums[2]=2,��L=2������ˣ���ô����Ҫ��L=2��R=R-1��λ��ֵ����Ϊ{1,2,9,4,2},R=4
                 * 2��val>R
                 * eg��{1,8,2,3,6}
                 * ��L=1,R=5ʱ����Ϊnums[1]=8,������Ч���ˣ���ʱ��Ҫ����
                 * 3��Ҫ������ֵ�Ѿ����ˣ�Ҳ��Ҫ����Ŀ���ǰ�R--
                 * eg��{1,2,3,2x}
                 */
                swap(L, --R, nums);
            } else {
                /**
                 * ֵ��L~R֮��Ľ���
                 * eg:{1,3,2,8,4,7,8,9}
                 * ��L=1,R=5
                 * ��Ϊ3����Ч��������ֻ��Ҫ����Ч��������R����Ҫ����
                 */
                swap(L, val - 1, nums);
            }
        }
        return R + 1;
    }

    private static void swap(int i, int j, int[] nums) {
        int val = nums[i];
        nums[i] = nums[j];
        nums[j] = val;
    }
}
